﻿#include <iostream>
using namespace std;

int n = 20;
int a[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };

int prime(int x) {                          //判断整数x是否素数
	int i, n;
	n = (int)sqrt(x);
	for(i = 2; i <= n; i++) {
		if(x % i == 0) {
			return 0;
		}
	}
	return 1;
}

int check(int k) {                          //判断位置k的填写是否满足约束条件
	int i;
	int flag = 0;
	for(i = 0; i < k; i++) {                //判断是否是重复
		if(a[i] == a[k]) {
			return 0;
		}
	}
	flag = prime(a[k] + a[k - 1]);          //判断相邻数之和是否素数
	if(flag == 1 && k == n - 1) {           //判断第一个和最后一个是否素数
		flag = prime(a[k] + a[0]);
	}

	return flag;
}

void primeCircle(int n) {                   //填写1~n共n个整数
	int i, k;
	for(i = 0; i < n; i++) {                //将数组a[n]初始化为0
		a[i] = 0;
	}
	a[0] = 1;
	k = 1;                       			//指定第0个位置填写1
	while(k >= 1) {
		a[k] = a[k] + 1;
		while(a[k] <= n) {
			if(check(k) == 1) {             //位置k可以填写整数a[k]
				break;
			} else {                        //试探下一个数
				a[k] = a[k] + 1;
			}
		}
		if(a[k] <= n && k == n - 1) {       //求解完毕，输出解
			for(i = 0; i < n; i++) {
				cout << a[i] << " ";
			}
			return;
		}
		if(a[k] <= n && k < n - 1) {
			k = k + 1;                      //填写下一个位置
		} else {
			a[k--] = 0;                     //回溯
		}
	}
}

int main() {
	primeCircle(20);

	system("pause");

	return 0;
}
